/**
 * @file memm1.c
 * 简单的堆管理
 * 可使用偏移量代替指针，即内存的地址允许被迁移并继续管理
 * 可自由指定堆位置
 * 可一次性全部释放内存
 * 允许从尾部开始申请内存
 * 使用从最小内存块分配策略
 *
 * @author lokliang
 * @brief
 * @version 0.2
 * @date 2022-12-07
 * @date 2022-01-14
 *
 * @copyright Copyright (c) 2022
 *
 */

#if !defined(CONFIG_MEMM_TYPE) || (CONFIG_MEMM_TYPE == 1)

#include "memm.h"
#include "sys_log.h"

#ifndef NULL
#define NULL ((void *)0)
#endif

#ifndef CONFIG_MEMM_NODE_TYPE
#define CONFIG_MEMM_NODE_TYPE 0 /* 0 使用指针连结（推荐）；1 使用偏移量连结，内存的地址允许被迁移并继续管理 */
#endif

#if CONFIG_MEMM_NODE_TYPE == 1

typedef struct
{
    signed next;       // 指向下一个已使用的内存块的管理地址
    size_t space_size; // 整个块的大小（包含本结构体和尾段的指针）
} memm_node_handle_t;  // 空闲内存的结构

typedef signed memm_node_t;

#else /* #if CONFIG_MEMM_NODE_TYPE == 1 */

typedef struct
{
    void *next;        // 指向下一个已使用的内存块的管理地址
    size_t space_size; // 整个块的大小（包含本结构体和尾段的指针）
} memm_node_handle_t;  // 空闲内存的结构

typedef memm_node_handle_t *memm_node_t;

#endif /* #if CONFIG_MEMM_NODE_TYPE == 1 */

typedef struct
{
    size_t space_size; // 整个块的大小（包含本结构体）

} memm_data_t; // 已申请内存的数据结构

typedef struct
{
    memm_node_t start; // 用户定义的内存的基地址
    memm_node_t end;   // 用户定义的内存的结束地址

    size_t free_total; // 统计总空闲数（包含所有碎片）

    void *addr_bank1[2];  // 用于 realloc 在 free 时的数据备份和恢复
    size_t data_bank1[2]; // 用于 realloc 在 free 时的数据备份和恢复
    size_t bank1_count;   // 用于 realloc 在 free 时的数据备份和恢复

    memm_node_handle_t data_bank2; // 用于 realloc 在 malloc 时的数据备份和恢复

    memm_node_handle_t free_node;

} memm_handle_t;

#define _MEMM_BLOCK_MANAGER_SPACE (sizeof(memm_data_t)) // 每个管理块额外消耗的字节数

/************************************************************************************************/

#if CONFIG_MEMM_NODE_TYPE == 1
#define _MEMM_GET_POINTER(DEV) ((memm_node_handle_t *)(&((uint8_t *)p_hdr)[DEV]))
#define _MEMM_GET_DEV_VALUE(P) ((size_t)(P) - (size_t)p_hdr)
#else
#define _MEMM_GET_POINTER(DEV) (DEV)
#define _MEMM_GET_DEV_VALUE(P) (P)
#endif

static void *_memm_malloc(memm_t *hdl, size_t size, signed tail);
static void *_memm_calloc(memm_t *hdl, size_t size, signed tail);
static void *_memm_realloc(memm_t *hdl, void *p, size_t newsize);

memm_t *memm_init(void *mem_base, size_t mem_size)
{
    memm_handle_t *p_hdr = (memm_handle_t *)mem_base;
    memm_node_t start = (memm_node_t)_MEMM_GET_DEV_VALUE(&p_hdr[1]);
    memm_node_t end = (memm_node_t)((((size_t)start) + mem_size - sizeof(memm_handle_t)) / sizeof(size_t) * sizeof(size_t));

    /* 使用内存对齐 */
    start = (memm_node_t)(((size_t)start + sizeof(size_t) - 1) / sizeof(size_t) * sizeof(size_t));
    end = (memm_node_t)(((size_t)start + mem_size - sizeof(memm_handle_t)) / sizeof(size_t) * sizeof(size_t));
    mem_size = (size_t)end - (size_t)start;

    /* 检查参数 */
    if (mem_size < sizeof(memm_node_handle_t))
    {
        SYS_LOG_WRN("Insufficient Space, header: %d bytes, block: %d bytes",
                    sizeof(memm_handle_t),
                    sizeof(memm_node_handle_t));
        return NULL;
    }

    p_hdr->start = start;
    p_hdr->end = end;

    memm_free_all((memm_t *)p_hdr);

    return (memm_t *)p_hdr;
}

/**
 * @brief
 *
 * @param hdl
 * @param size
 * @return void* 0 -- 内存不足, != NULL -- 申请到的空间地址
 */
void *memm_malloc(memm_t *hdl, size_t size)
{
    return _memm_malloc(hdl, size, 0);
}

void *memm_calloc(memm_t *hdl, size_t size)
{
    return _memm_calloc(hdl, size, 0);
}

void *memm_malloc_tail(memm_t *hdl, size_t size)
{
    return _memm_malloc(hdl, size, 1);
}

void *memm_realloc(memm_t *hdl, void *p, size_t newsize)
{
    if (p == NULL)
    {
        return _memm_malloc(hdl, newsize, 0);
    }
    else
    {
        return _memm_realloc(hdl, p, newsize);
    }
}

int memm_free(memm_t *hdl, void *p)
{
    if (hdl == NULL || p == NULL)
    {
        return -1;
    }
    else
    {
#if (CONFIG_SYS_LOG_WRN_ON == 1)
        if (memm_is_valid(hdl, p) == false)
        {
            SYS_LOG_WRN("Memory attribute error: %p", p);
            return -1;
        }
#endif /* #if (CONFIG_SYS_LOG_WRN_ON == 1) */

        memm_handle_t *p_hdr = (memm_handle_t *)hdl;
        memm_node_handle_t *end_node = _MEMM_GET_POINTER(p_hdr->end);
        memm_data_t data_block = ((memm_data_t *)p)[-1];
        memm_node_handle_t *free_block_test = (memm_node_handle_t *)&((memm_data_t *)p)[-1];
        memm_node_handle_t *free_block_prev = &p_hdr->free_node;
        memm_node_handle_t *free_block_next;
        do
        {
            free_block_next = _MEMM_GET_POINTER(free_block_prev->next);
            if (free_block_next < free_block_test)
            {
                free_block_prev = free_block_next;
            }
            else
            {
                break;
            }
        } while (free_block_next < end_node);

#define _BLOCK_END(P) ((memm_node_handle_t *)&((uint8_t *)P)[(P)->space_size])
#define _DATA_BANK(M)                                                                  \
    if (p_hdr->bank1_count < sizeof(p_hdr->addr_bank1) / sizeof(p_hdr->addr_bank1[0])) \
    {                                                                                  \
        p_hdr->addr_bank1[p_hdr->bank1_count] = &M;                                    \
        p_hdr->data_bank1[p_hdr->bank1_count] = (size_t)M;                             \
        p_hdr->bank1_count++;                                                          \
    }

        if (_BLOCK_END(&((memm_data_t *)p)[-1]) == free_block_next) // 数据块的结尾与下个空白块相邻
        {
            if (_BLOCK_END(free_block_prev) == free_block_test && free_block_prev != &p_hdr->free_node) // 上个空白块的结尾与数据块相邻，并且不是链头
            {
                /* 首尾都相邻 */

                _DATA_BANK(free_block_prev->space_size);
                _DATA_BANK(free_block_prev->next);

                if (free_block_next < end_node)
                {
                    /* 合并前后两个空闲块 */
                    free_block_prev->space_size = free_block_prev->space_size + data_block.space_size + free_block_next->space_size;
                    free_block_prev->next = free_block_next->next;
                }
                else
                {
                    /* 仅合并前一个空闲块 */
                    free_block_prev->space_size = free_block_prev->space_size + data_block.space_size;
                    free_block_prev->next = _MEMM_GET_DEV_VALUE(end_node);
                }
            }
            else // 上个空白块的结尾与数据块不相邻
            {
                /* 仅与下一块相邻 */

                if (free_block_next < end_node)
                {
                    /* 仅合并后一个空闲块 */
                    free_block_test->space_size = data_block.space_size + free_block_next->space_size;
                    free_block_test->next = free_block_next->next;
                }
                else
                {
                    /* 当前是最后结尾的一块 */
                    free_block_test->space_size = data_block.space_size;
                    free_block_test->next = _MEMM_GET_DEV_VALUE(end_node);
                }

                _DATA_BANK(free_block_prev->next);

                free_block_prev->next = _MEMM_GET_DEV_VALUE(free_block_test);
            }
        }
        else // 数据块的结尾与下个空白块不相邻
        {
            if (_BLOCK_END(free_block_prev) == free_block_test && free_block_prev != &p_hdr->free_node) // 上个空白块的结尾与数据块相邻，并且不是链头
            {
                /* 仅与上一块相邻 */

                _DATA_BANK(free_block_prev->space_size);

                free_block_prev->space_size = free_block_prev->space_size + data_block.space_size;
            }
            else // 上个空白块的结尾与数据块不相邻
            {
                /* 不相邻 */

                _DATA_BANK(free_block_prev->next);

                free_block_test->space_size = data_block.space_size;
                free_block_test->next = _MEMM_GET_DEV_VALUE(free_block_next);
                free_block_prev->next = _MEMM_GET_DEV_VALUE(free_block_test);
            }
        }

        p_hdr->free_total += data_block.space_size;
    }

#undef _BLOCK_END
#undef _DATA_BANK

    return 0;
}

void memm_free_all(memm_t *hdl)
{
    memm_handle_t *p_hdr = (memm_handle_t *)hdl;
    memm_node_t start = p_hdr->start; // 用户定义的内存的基地址
    memm_node_t end = p_hdr->end;     // 用户定义的内存的结束地址

    /* 初始化 *p_hdr */
    memset(p_hdr, 0, sizeof(*p_hdr));
    p_hdr->start = start;
    p_hdr->end = end;
    p_hdr->free_node.next = start;
    p_hdr->free_node.space_size = sizeof(p_hdr->free_node);
    p_hdr->free_total = (size_t)end - (size_t)start;

    memm_node_handle_t *free_node = _MEMM_GET_POINTER(start);
    free_node->next = end;
    free_node->space_size = (size_t)end - (size_t)start;
}

size_t memm_used_size(memm_t *hdl)
{
    memm_handle_t *p_hdr = (memm_handle_t *)hdl;

    return ((size_t)p_hdr->end - (size_t)p_hdr->start - p_hdr->free_total);
}

size_t memm_free_size(memm_t *hdl)
{
    memm_handle_t *p_hdr = (memm_handle_t *)hdl;
    return p_hdr->free_total - _MEMM_BLOCK_MANAGER_SPACE;
}

size_t memm_block_max(memm_t *hdl)
{
    memm_handle_t *p_hdr = (memm_handle_t *)hdl;
    memm_node_handle_t *p_test_block = &p_hdr->free_node;
    memm_node_handle_t *end_node = _MEMM_GET_POINTER(p_hdr->end);

    if ((size_t)_MEMM_GET_POINTER(p_test_block->next) < (size_t)end_node)
    {
        size_t ret = _MEMM_BLOCK_MANAGER_SPACE;

        do
        {
            if (ret < p_test_block->space_size)
            {
                ret = p_test_block->space_size;
            }
            p_test_block = _MEMM_GET_POINTER(p_test_block->next);
        } while (p_test_block < end_node);

        return ret - _MEMM_BLOCK_MANAGER_SPACE;
    }
    else
    {
        return 0;
    }
}

bool memm_is_valid(memm_t *hdl, void *p)
{
    if (hdl == NULL || p == NULL)
    {
        return false;
    }
    else
    {
        memm_handle_t *p_hdr = (memm_handle_t *)hdl;
        memm_data_t *p_data_block = &((memm_data_t *)p)[-1];

        if ((size_t)p_data_block < (size_t)_MEMM_GET_POINTER(p_hdr->start) ||
            (size_t)p_data_block >= (size_t)_MEMM_GET_POINTER(p_hdr->end))
        {
            return false;
        }
    }
    return true;
}

size_t memm_get_header_info_size(void)
{
    return sizeof(memm_handle_t);
}

size_t memm_get_block_info_size(void)
{
    return _MEMM_BLOCK_MANAGER_SPACE;
}

size_t memm_get_data_space_size(void *p)
{
    return ((&((memm_data_t *)(p))[-1])->space_size - _MEMM_BLOCK_MANAGER_SPACE);
}

void *memm_get_base(memm_t *hdl)
{
    memm_handle_t *p_hdr = (memm_handle_t *)hdl;
    return _MEMM_GET_POINTER(p_hdr->start);
}

void *memm_get_end(memm_t *hdl)
{
    memm_handle_t *p_hdr = (memm_handle_t *)hdl;
    return _MEMM_GET_POINTER(p_hdr->end);
}

static void *_memm_malloc(memm_t *hdl, size_t size, signed tail)
{
    memm_handle_t *p_hdr = (memm_handle_t *)hdl;
    memm_node_handle_t *end_node = _MEMM_GET_POINTER(p_hdr->end);
    memm_node_handle_t *free_block_prev = &p_hdr->free_node;
    memm_node_handle_t *free_block_next;
    memm_node_handle_t *test_block = _MEMM_GET_POINTER(free_block_prev->next);
    memm_node_handle_t *best_block = NULL;
    memm_node_handle_t *best_block_prev = NULL;
    memm_data_t *data_block;
    size_t alloc_space;

    if (size < sizeof(memm_node_handle_t) - sizeof(memm_data_t))
    {
        size = sizeof(memm_node_handle_t) - sizeof(memm_data_t);
    }

    // 确定真正需要分配的大小
    alloc_space = (size + _MEMM_BLOCK_MANAGER_SPACE + (sizeof(size_t) - 1)) / sizeof(size_t) * sizeof(size_t);

    if (tail == 0)
    {
        size_t best_space = ~0;

        // 在可分配的空间内搜索有足够空间的链
        while (test_block < end_node)
        {
            // 空间足够，并且在分配后剩余足够最少一个连接的空间
            if (test_block->space_size >= alloc_space)
            {
                if (best_space > test_block->space_size)
                {
                    best_block = test_block;
                    best_block_prev = free_block_prev;
                    best_space = test_block->space_size;
                    if (best_space == alloc_space)
                    {
                        break;
                    }
                }
            }

            free_block_prev = test_block;
            test_block = _MEMM_GET_POINTER(test_block->next);
        }

        if (best_block != NULL)
        {
            data_block = (memm_data_t *)best_block;

            free_block_next = (memm_node_handle_t *)&((uint8_t *)best_block)[alloc_space];
            p_hdr->data_bank2 = *free_block_next;

            if (best_block->space_size >= alloc_space + sizeof(memm_node_handle_t)) // 空间足够，并且在分配后剩余足够最少一个连接的空间
            {
                // 处理被拆开后的新空闲块
                free_block_next->space_size = best_block->space_size - alloc_space;
                free_block_next->next = best_block->next;

                // 连接到新的空闲块
                best_block_prev->next = _MEMM_GET_DEV_VALUE(free_block_next);

                // 更新和标记信息
                data_block->space_size = alloc_space;

                p_hdr->free_total -= alloc_space;
            }
            else // 空间足够，但在分配后剩余的空间不路一个连接所需要的空间
            {
                // 连接到下个空闲块
                best_block_prev->next = best_block->next;

                // 更新和标记信息
                data_block->space_size = best_block->space_size;

                p_hdr->free_total -= best_block->space_size;
            }

            return ((void *)&data_block[1]);
        }
    }
    else // tial != NULL
    {
        // 在可分配的空间内搜索有足够空间的链
        while (test_block < end_node)
        {
            // 空间足够，并且在分配后剩余足够最少一个连接的空间
            if (test_block->space_size >= alloc_space)
            {
                best_block = test_block;
                best_block_prev = free_block_prev;
            }

            free_block_prev = test_block;
            test_block = _MEMM_GET_POINTER(test_block->next);
        }

        if (best_block != NULL)
        {
            if (best_block->space_size >= alloc_space + sizeof(memm_node_handle_t)) // 空间足够，并且在分配后剩余足够最少一个连接的空间
            {
                // 处理被拆开后的新空闲块
                free_block_next = (memm_node_handle_t *)&((uint8_t *)best_block)[0];
                free_block_next->space_size = best_block->space_size - alloc_space;

                // 连接到新的空闲块
                best_block_prev->next = _MEMM_GET_DEV_VALUE(free_block_next);

                // 更新和标记信息
                data_block = (memm_data_t *)&((uint8_t *)best_block)[free_block_next->space_size];
                data_block->space_size = alloc_space;

                p_hdr->free_total -= alloc_space;
            }
            else // 空间足够，但在分配后剩余的空间不路一个连接所需要的空间
            {
                // 连接到下个空闲块
                best_block_prev->next = best_block->next;

                // 更新和标记信息
                data_block = (memm_data_t *)best_block;
                data_block->space_size = best_block->space_size;

                p_hdr->free_total -= best_block->space_size;
            }

            return ((void *)&data_block[1]);
        }
    }

    return NULL;
}

static void *_memm_calloc(memm_t *hdl, size_t size, signed tail)
{
    void *ret;

    ret = _memm_malloc(hdl, size, tail);
    if (ret == NULL)
    {
        return NULL;
    }

    memset(ret, 0, size);

    return ret;
}

static void *_memm_realloc(memm_t *hdl, void *p, size_t newsize)
{
#if (CONFIG_SYS_LOG_WRN_ON == 1)
    if (memm_is_valid(hdl, p) == false)
    {
        SYS_LOG_WRN("Memory attribute error: %p", p);
        return NULL;
    }
#endif /* #if (CONFIG_SYS_LOG_WRN_ON == 1) */

    if (p == NULL)
    {
        return memm_malloc(hdl, newsize);
    }

    if (newsize == 0)
    {
        memm_free(hdl, p);
        return NULL;
    }

    memm_handle_t *p_hdr = (memm_handle_t *)hdl;
    memm_data_t *p_data_block = &((memm_data_t *)p)[-1];
    memm_node_handle_t node_bank = *((memm_node_handle_t *)p_data_block); // 备份用户空间头信息
    size_t free_total = p_hdr->free_total;
    void *ret;

    /* 使空间大小按要求对齐 */
    newsize = (newsize + sizeof(size_t) - 1) / sizeof(size_t) * sizeof(size_t);
    if (newsize == p_data_block->space_size - _MEMM_BLOCK_MANAGER_SPACE)
    {
        return p;
    }

    // 释放空间
    p_hdr->bank1_count = 0; // 使 memm_free() 的备份功能生效
    if (memm_free(hdl, p))
    {
        return NULL;
    }

    // 申请空空间
    ret = memm_malloc(hdl, newsize);
    if (ret == NULL) // 申请失败
    {
        // 还原信息
        for (size_t i = 0; i < p_hdr->bank1_count; i++)
        {
            *(size_t *)p_hdr->addr_bank1[i] = p_hdr->data_bank1[i];
        }
        memcpy(p_data_block, &node_bank, sizeof(node_bank));
        p_hdr->free_total = free_total;
        return NULL;
    }

    if (ret != p) // 申请了新位置
    {
        size_t real_size = newsize;

        p_data_block = (memm_data_t *)&node_bank;
        if (real_size > p_data_block->space_size - _MEMM_BLOCK_MANAGER_SPACE)
            real_size = p_data_block->space_size - _MEMM_BLOCK_MANAGER_SPACE;

        for (size_t i = 0; i < real_size / sizeof(size_t); i++)
            ((size_t *)ret)[i] = ((size_t *)p)[i];

        if ((size_t)ret + newsize >= (size_t)p && (size_t)ret + newsize < (size_t)p + real_size)
        {
            size_t cover_offset = (size_t)ret + newsize - (size_t)p;
            int cover_size = real_size - cover_offset;
            if (cover_size > sizeof(p_hdr->data_bank2))
                cover_size = sizeof(p_hdr->data_bank2);
            if (cover_size > real_size)
                cover_size = real_size;

            memcpy(&((uint8_t *)ret)[cover_offset], &p_hdr->data_bank2, cover_size);
        }
    }

    memcpy(ret, &((uint8_t *)&node_bank)[sizeof(memm_data_t)], sizeof(memm_node_handle_t) - sizeof(memm_data_t));

    return ret;
}

#endif /* #if !defined(CONFIG_MEMM_TYPE) || (CONFIG_MEMM_TYPE == 1) */
